home *** CD-ROM | disk | FTP | other *** search
/ The World of Computer Software / The World of Computer Software.iso / lnklst10.zip / LINKLIST.C next >
C/C++ Source or Header  |  1993-01-19  |  5KB  |  216 lines
  1. /*
  2.  * LINKLIST.C: Functions for implementing a linked-list array.
  3.  *
  4.  * All code is (c) Copyright 1993 Ben Morris and SpeedSOFT Development.
  5.  * Ben Morris Retains all intellectual rights and copyrights to this
  6.  * code.  Under no circumstances is the author's name to be removed from
  7.  * the header file, source file or object code created by compiling the
  8.  * source code.
  9.  *
  10.  * Other than the above restriction, this code may be used freely with
  11.  * any software, commercial or otherwise.
  12.  *
  13.  * Ben Morris also disclaims all warranties, express or implied, with
  14.  * regards to the fitness of this code for any purpose.  Under no
  15.  * circumstances shall Ben Morris or SpeedSOFT Development be held liable
  16.  * for any damages, losses, or claim for loss of profit, resulting from
  17.  * the use or inability to use this software and all accompanying
  18.  * documentation.
  19.  *
  20.  */
  21.  
  22. #include "linklist.h"
  23.  
  24. static char *copyright = "Linked Lists by Ben Morris, SSD";
  25.  
  26. /*---------------------------------------------------------------------------*/
  27.  
  28. NODEPTR InitList( void )
  29. /*
  30.  * Initializes the linked list.  Returns NULL or a pointer to the
  31.  * head node.
  32.  *
  33.  */
  34. {
  35.     NODEPTR ndp;
  36.  
  37.     /* Allocate space */
  38.     ndp = malloc( sizeof( NODE ) );
  39.  
  40.     if( ndp == NULL )
  41.         return NULL;
  42.  
  43.     /* Now setup the head node */
  44.     ndp->next = ndp;
  45.     ndp->prev = ndp;
  46.     ndp->data = NULL;
  47.  
  48.     return ndp;
  49. }
  50.  
  51. /*---------------------------------------------------------------------------*/
  52.  
  53. NODEPTR NodeInsert( NODEPTR prev_ndp, size_t size )
  54. /*
  55.  * Inserts a node in the linked list AFTER prev_ndp, and allocates its
  56.  * 'data' member with 'size'.
  57.  *
  58.  * RETURNS NULL on fail, or NODEPTR on success.
  59.  *
  60.  */
  61. {
  62.     NODEPTR ndp, tmp = prev_ndp->next;
  63.  
  64.     /* Allocate space */
  65.     ndp = malloc( sizeof( NODE ) );
  66.  
  67.     if( ndp == NULL )   /* No space for NODE! */
  68.         return NULL;
  69.  
  70.     if( size )
  71.     {
  72.         ndp->data = malloc( size );
  73.         if( ndp->data == NULL ) /* No space for DATA! */
  74.         {
  75.             free( ndp );
  76.             return NULL;
  77.         }
  78.     }
  79.     else
  80.         ndp->data = NULL;
  81.  
  82.     /*
  83.      * Since we're inserting AFTER prev_ndp, we have to set
  84.      * ndp's 'next' to prev_ndp's 'next'.
  85.      *
  86.      * ndp's 'prev' becomes 'prev_ndp'.
  87.      *
  88.      */
  89.  
  90.     /* If true, prev_ndp is the last node. */
  91.     if( tmp->prev == prev_ndp )
  92.         tmp->prev = ndp;
  93.  
  94.     ndp->next = prev_ndp->next;
  95.     ndp->prev = prev_ndp;
  96.     prev_ndp->next = ndp;
  97.  
  98.     return ndp;
  99.  
  100. }
  101.  
  102. /*---------------------------------------------------------------------------*/
  103.  
  104. void NodeDelete( NODEPTR ndp )
  105. /*
  106.  * Deletes 'ndp' from the linked list and frees its storage, if any.
  107.  *
  108.  */
  109. {
  110.     NODEPTR prev = ndp->prev;
  111.     NODEPTR next = ndp->next;
  112.  
  113.     prev->next = next;
  114.     next->prev = prev;
  115.  
  116.     if( ndp->data )
  117.         free( ndp->data );
  118.     free( ndp );
  119. }
  120.  
  121. /*---------------------------------------------------------------------------*/
  122.  
  123. NODEPTR NodeNumtoPtr( int num, NODEPTR head_ndp )
  124. /*
  125.  * Converts num to the corresponding node in the list, starting at 0.
  126.  *
  127.  */
  128. {
  129.     int     i;
  130.     NODEPTR last = NodeLast( head_ndp ), ndp;
  131.  
  132.     ndp = NodeNext( head_ndp );
  133.  
  134.     /*
  135.      * Loop until we hit 'num', or until the current pointer is 'last', in
  136.      * which case we return 0.
  137.      *
  138.      */
  139.     for( i = 0; i <= num; i++ )
  140.     {
  141.         if( i == num )
  142.             return ndp;
  143.         if( ndp == last )
  144.             return NULL;
  145.         ndp = NodeNext( ndp );
  146.     }
  147.  
  148.     return NULL;
  149.  
  150. }
  151.  
  152. /*---------------------------------------------------------------------------*/
  153.  
  154. int NodePtrtoNum( NODEPTR sndp, NODEPTR head_ndp )
  155. /*
  156.  * Returns ndp's number in the linked list.
  157.  *
  158.  */
  159. {
  160.     int     i;
  161.     NODEPTR last = NodeLast( head_ndp ), ndp;
  162.  
  163.     ndp = NodeNext( head_ndp );
  164.  
  165.     /*
  166.      * Loop until ndp == sndp, in which case we return 'i'.  If not found,
  167.      * return -1.
  168.      *
  169.      */
  170.     for( i = 0; ; i++ )
  171.     {
  172.         if( ndp == sndp )
  173.             return i;
  174.         if( ndp == last )
  175.             return -1;
  176.         ndp = NodeNext( ndp );
  177.     }
  178.  
  179. }
  180.  
  181. /*---------------------------------------------------------------------------*/
  182.  
  183. void DestroyList( NODEPTR head_ndp )
  184. /*
  185.  * Destroys the linked list by freeing all allocated memory in every node
  186.  * (including the head node!)
  187.  *
  188.  */
  189. {
  190.     NODEPTR ndp, last = NodeLast( head_ndp );
  191.     int     breakit = 0;
  192.  
  193.     ndp = NodeNext( head_ndp );
  194.  
  195.     /*
  196.      * Loop until we hit 'num', or until the current pointer is 'last', in
  197.      * which case we return 0.
  198.      *
  199.      */
  200.     for( ;; )
  201.     {
  202.         if( ndp == last )
  203.             breakit = 1;
  204.         if( ndp->data != NULL )
  205.             free( ndp->data );
  206.         free( ndp );
  207.         if( breakit )
  208.             break;
  209.         ndp = NodeNext( ndp );
  210.     }
  211.  
  212.     free( head_ndp );
  213.  
  214. }
  215.  
  216.